/*
实验5-4 根据后序和中序遍历输出前序遍历
分数 25
作者 DS课程组
单位 浙江大学

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的前序遍历结果。
输入格式:

第一行给出正整数 n (≤30)，是树中结点的个数。随后两行，每行给出 n 个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。
输出格式:

在一行中输出Preorder: 以及该树的前序遍历结果。数字间有1个空格，行末不得有多余空格。
输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

Preorder: 4 1 3 2 6 5 7
*/

#include <iostream>

using namespace std;

// 根据后序遍历和中序遍历结果输出前序遍历结果
void Preorder(int *post, int *in, int n) {
    if (n == 0) {
        return; // 如果没有节点，直接返回
    }
    int root = post[n-1]; // 后序遍历的最后一个节点是根节点
    cout << " " << root; // 输出根节点
    int i;
    for (i=0; i<n; i++) {
        if (in[i] == root) {
            break; // 在中序遍历中找到根节点的位置
        }
    }
    Preorder(post, in, i); // 递归处理左子树
    Preorder(post+i, in+i+1, n-i-1); // 递归处理右子树
}

int main() {
    int n;
    cin >> n; // 输入节点个数
    int post[30], in[30];
    for (int i=0; i<n; i++) {
        cin >> post[i]; // 输入后序遍历结果
    }
    for (int i=0; i<n; i++) {
        cin >> in[i]; // 输入中序遍历结果
    }
    cout << "Preorder:";
    Preorder(post, in, n); // 输出前序遍历结果
    cout << endl;
    return 0;
}